// https://www.lintcode.com/problem/next-permutation/

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers
     */
    public int[] nextPermutation(int[] nums) {
        // write your code here
        /*
          以162543为例，下一个应该是163245。
          步骤如下：
          1. 找到最后一个num[i] < num[i + 1]的点
          2. 如果没找到，说明已经是最后一个排列，逆序返回即可。
          3. 从num[i + 1]到num[-1]找到大于num[i]的最小数，并与num[i]交换位置。
          4. 对num[i + 1]到num[-1]排序
        */
        int i = nums.length - 2;
        while (i >= 0) {
            if (nums[i] < nums[i + 1]) {
                break;
            }
            --i;
        }
        if (i < 0) {
            int start = 0, end = nums.length - 1;
            while (start < end) {
                int t = nums[start];
                nums[start] = nums[end];
                nums[end] = t;
                ++start;
                --end;
            }
        } else {
            int[] partial = new int[nums.length - (i + 1)];
            int min_val = nums[i + 1];
            int min_pos = i + 1;
            for (int j = i + 2; j < nums.length; ++j) {
                if ((nums[j] < min_val) && (nums[j] > nums[i])) {
                    min_val = nums[j];
                    min_pos = j;
                }
            }
            int t = nums[i];
            nums[i] = nums[min_pos];
            nums[min_pos] = t;
            for (int j = i + 1; j < nums.length; ++j) {
                partial[j - (i + 1)] = nums[j];
            }
            Arrays.sort(partial);
            for (int j = i + 1; j < nums.length; ++j) {
                nums[j] = partial[j - (i + 1)];
            }
        }
        return nums;
    }
}